package cn.xiaolang.function.data_structure;

/**
 * 剑指 Offer 14- I. 剪绳子 https://leetcode.cn/problems/jian-sheng-zi-lcof/
 * 给你一根长度为n的绳子，请把绳子剪成整数长度的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。
 * 请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
 * 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 * <p>
 * 示例 1：
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1
 * <p>
 * 示例 2:
 * 输入: 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
 * <p>
 * 提示：
 * 2 <= n <= 58
 */
public class No23CuttingRope {

    public static void main(String[] args) {
        No23CuttingRope algorithm = new No23CuttingRope();
        int re = algorithm.cuttingRope(8);
        System.out.println(re);

    }


    /**
     * 创建数组dp，其中dp[i]表示将正整数i拆分成至少两个正整数的和之后，这些正整数的最大乘积。
     * 特别地，0不是正整数，1是最小的正整数，0和1都不能拆分，因此dp[0]=dp[1]=0。
     * <p>
     * 当i≥2时，假设对正整数i拆分出的第一个正整数是 j（1≤j<i），则有以下两种方案：
     * <ui>将i拆分成j和i−j的和，且i−j不再拆分成多个正整数，此时的乘积是 j×(i−j)</ui>
     * <ui>将i拆分成j和i−j的和，且i−j继续拆分成多个正整数，此时的乘积是 j×dp[i−j]</ui>
     *
     * dp[i] = Math.max(j*(i-j)，j*dp(i-j))
     * dp[2] = Math.max(1*1，1*dp(1)) = 1
     * dp[3] = Math.max(1*2，1*dp(2)) = 2
     * dp[4] = Math.max(1*3，1*dp(3)) .. Math.max(2*2，2*dp(2))
     */
    public int cuttingRope(int n) {
        if (n < 2 || n > 58) {
            return 0;
        }
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
}
